/*
2021/10/30
二分搜索树头文件
依旧手写注释
主要代码copy自课本
*/

#ifdef _BST_H
#define _BST_H

#include<iostream>
#include<new>
#include<vector>
#include<fstream>
#include<functional>
#include<ctime>
#include<algorithm>
//还不知道应该include哪些，到时候出问题了再说,想到的都写了，出问题再说

template<typrname Comparable>
//定义模板类

class BinarySearchTree
{
 public:
  BinarySearchTree();
  BinarySearchTree(const BinarySearchTree & rhs);
  BinarySearchTree(BinarySearchTree &&rhs);
  ~BinarySearchTree();
  //所有构造函数的具体内容我按照菜鸟教程中给出的另一种写法（BinarySearchTree：：BinarySearchTree（啊巴啊巴））写在底下，这样可读性应该强一点
  //以上是类的构造和析构函数，同时也允许你copy一个已有的tree

  const Comparable & findMin() const;
  const Comparable & findMax() const;
  //寻找最大值和最小值
  bool contains(const Comparable & x);
  //判断这棵树是有节点存储着需要找的数据
  bool contains(const Comparable & x)
  {
    return contains(x,root);
  }
  //引用一下

  
  bool isEmpty() const
  {
    if(root == nullptr)
      return true;
    else
      return false;
  }
  //判断一棵树是否是空树
  void printTree(ostream & out =cout) const
  {
    if (isEmpty())
      out<< "It is Empty!" <<endl;
    else
      printTree(root,out);
  }
  //打印这个树
  
  void makeEmpty()
  {
    makeEmpty(root);
  }
  //建立一棵空树
  void insert(const Comparable & x)
  {
    insert(x,root);
  }
  void insert(Comparable && x)
  {
    insert(x,root);
  }
  //两种参数调用类型的函数，用来实现插入一个数据的动作
  void remove(const Comparable & x )
  {
    remove(x,root);
  }
  //从数中去除一个节点
  //public中的这些函数都是引用private的，也就是所谓二重封装。
  BinarySearchTree & operator= (const BinarySearchTree & rhs);
  BinarySearchTree & operator= (BinarySearchTree && rhs);
  //似乎用不到，虽然给的课本里给的模板有，但是不写了
  //重载操作
  vector<Comparable> CoverInMid(BinaryNode* t,vector<Comparable> data)const;
  //中序遍历，然后覆盖vector，就叫这个名字算了...
  vector<Comparable> LetUsRandomIt (vector<Comparable> data);
  //突然中二了起来
 private:
  struct BinaryNode
  {
    Comparable element;
    Binarynode *left;
    Binarynode *right;

    BinaryNode(const Comparable & theElement,BinaryNode *lt,BinaryNode *rt)
      :element{theElement},left{lt},right{rt}{}
    BinaryNode(Comparable && theElement,BinaryNode *lt,BinaryNode *rt)
      :element{std::move(theElement)},left{lt},right{rt}{}
  };
  //定义结构体，这个结构体就是二叉树上的一个节点，其中element是它的内容，left和right指针分别指向它的左叶和右叶
  
  BinaryNode *root;
  //定义根节点，我们的操作一般从根节点开始向下检索

  //所有方法都在private里被重新封装了一次
  //有课本可以抄真好
  //可惜书本附带的源代码下载不了，还是得手打，哭
  void insert(const Comparable & x,BinaryNode * & t)
  {
    if (t==nullptr)
      t = new BinaryNode(x,nullptr,nullptr);
    //建立新叶子
    else if (x < t -> right)
      insert(x,t->right);
    else if (t->element < x)
      insert(x,t->right);
    else
      ;
  }
  
  void insert(Comparable && x,BinaryNode * & t)
  {
    if (t == nullptr)
      t = new BinaryNode{ std::move(x),nullptr,nullptr };
    else if (x < t->element)
      insert(std::move(x), t->left);
    else if (t->element < x)
      insert(std::move(x), t->right);
     else
    ;//do  nothing

  }
  void remove(const Comparable & x,BinaryNode *t) const
  {
    if (t == nullptr)
      return;
    if (x < t->element)
      remove(x, t->left);
    else if (t->element < x)
      remove(x, t->right);
    else if (t->left != nullptr && t->right != nullptr)
      {
	t->element = findMin(t->right)->element;
	remove(t->element, t->right);
      }
    else
      {
	BinaryNode * oldNode = t;
	t = (t->left != nullptr) ? t->left : t->right;
	delete oldNode;
     }
    //照抄书本的懒惰删除；
  }
  BinaryNode * FindMin(BinaryNode * & t);
  BinaryNode * FindMax(BinaryNode * & t);
  //似乎用不到，那就不写了
  bool contains(const Comparable & x,BinaryNode *t) const
  {
    if (t == nullptr)
      return false;
    else if (x < t->element)
      return contains(x, t->left);
    else if (t->element < x)
      return contains(x, t->right);
    else
      return true;
  }
  void makeEmpty(BinaryNode * & t)
  {
    if (t != nullptr)
      {
	makeEmpty(t->left);
	makeEmpty(t->right);
	delete t;
      }
    t = nullptr;
  }
  void printTree(BinaryNode * t) const
  {
    if (t != nullptr)
      {
	printTree(t->left, out);
	out << t->element << endl;
	printTree(t->right, out);
      }

  }
  //二叉树各种功能的private版本
}

//以下给出构造函数和析构函数的内容
BinarySearchTree::BinarySearchTree()
{
  root = nullptr;
}
//标准的初始化函数
BinarySearchTree::BinarySearchTree(const BinarySearchTree & rhs) :root{nullptr}
{
  root=clone(rhs.root);
}
BinarySearchTree::BinarySearchTree(const BinarySearchTree & rhs):root{nullptr}
{
  root = clone(rhs.root);
}
//用来复制或者移动的构造函数

BinarySearchTree::~BinarySeaerchTree()
{
  makeEmpty();
}
//析构函数，擦屁股用,（笑）

//额 想起来要写homework的要求，还得写个方法来随机覆盖和乱序排列，顺便学下vector容器的用法...
//我上课说实话挺容易走神的，还得自己摸索
BinarySearchTree::vector<Comparable> CoverInMid(BinaryNode* t,vector<Comparable> data)const
{
  if (t==nullptr)
    return data;
  else
    {
      data = CoverInMid(t ->left,data);
      data.push_back(t->element);
      //顺便查了一下pushback咋用，反正会忘掉的...
      data =cover(t->right,data);
      return data;
}
  BinarySearchTree::vector<Comparable> LetUsRandomIt (vector<Comparable> data)
  {
    random_shuffle(data.begin(),data.end());
    //让我们摇一下这个容器，突然联想到调酒
    //调制饮料，改变人生（笑）
    //Vodka Martini，Shaken，Not Stirred
  }
  //不知道要不要初始化随机数，我不太懂机理，看CDSN上讲例子时没用

  //开始写要求里的两个函数
  vector<Comparable> BST_sort(std::vector<Comparable> &_data)
  {
    int n = _data.size();
    for (int i = 0; i < n; i++)
      {
	BinarySearchTree.insert(_data[i]);
      };
    _data.clear();
    _data = cover(root, _data);

    return _data;
  };
  //既然说要_data那就用这个吧
  //其实我不太确定自己写的似乎不是中序遍历
  vector<Comparable> Randomized_BST_sort(std::vector<Comparable> &_data)
  {
    _data =LetUsRandomIt(_data);
    cout << "out put the ramdomized data  "<< endl;
    for (int i = 0; i < _data.size(); i++)
      {
	cout << _data[i] << "     ";
      }
    cout << endl;
    _data = BST_sort(_data);
    return _data;
	};



#else
//DO NOTHING
#endif
